{
  // 3.输出字符串中所有的叠词（几个连续出现的字组成叠词）
  // 输入： '晴川历历汉阳树，芳草萋萋鹦鹉洲'
  // 输出： [ '历历', '萋萋' ]
  function getOverlapStr(str) {
    var result = [];
    for (var i = 0; i < str.length; i++) {
      if (str[i] === str[i + 1]) {
        result.push(str.slice(i, i + 2));
      }
    }
    return result;
  }
  // console.log(getOverlapStr('晴川历历汉阳树，芳草萋萋鹦鹉洲'))
}

{
  // 买卖股票的最佳时机
  // 假设有一个数组，它的第i个元素对应第i天的价格，如果最多只允许完成一次交易（即买进一次卖出一次），设计一个算法找出最大利润
  // 例：[7,1,5,3,6,4] 最大利润：5
  function getMaxProfit(arr) {
    var max = 0; // 最大值
    // 双指针 i j
    var i = 0;
    var j = 1;
    while (j < arr.length) {
      // 后一个值减去前一个值小于0时，i = j, j指针++
      if (arr[j] - arr[i] < 0) {
        i = j;
        j++;
      } else {
        // 后一个值大于前一个值才有可能出现最大值
        if (arr[j] - arr[i] > max) {
          max = arr[j] - arr[i];
        }
        j++;
      }
    }
    return max;
  }

  // 暴力群举法
  function getMaxProfit(arr) {
    let max = 0;
    for (let i = 0; i < arr.length; i++) {
      for (let j = i + 1; j < arr.length; j++) {
        if (arr[j] > arr[i]) {
          max = Math.max(max, arr[j] - arr[i]);
        }
      }
    }
    return max;
  }

  // 一个变量minprice存储 历史最低价
  // 一个变量max存储 最大利润
  //  遍历整个数组，有两种可能
  // 当前值小于历史最低价，则更新历史最低价
  // 当前值大于历史最低价，则取 [当前值-历史最低价]与 最大利润之间的较大值，更新 最大利润
  function getMaxProfit(arr) {
    let minPrice = arr[0];
    let max = 0;
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] < minPrice) {
        minPrice = arr[i];
      } else {
        max = Math.max(max, arr[i] - minPrice);
      }
    }
    return max;
  }
  console.log(getMaxProfit([7, 1, 5, 3, 6, 4]));
}

{
  // 打印出 1-1000000 之间的所有对称数(例如 121、1331 等)
  function isSymNum(start, end) {
    var arr = [];
    for (var i = start; i < end; i++) {
      // 解法有点类似回文串
      var num = +i.toString().split('').reverse().join('');
      if (i > 10 && num === i) {
        arr.push(num);
      }
    }
    return arr;
  }
  // console.log(isSymNum(1, 1000000))
}

{
  // 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
  // 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

  // 示例:
  // 给定 nums = [2, 7, 11, 15], target = 9
  // 因为 nums[0] + nums[1] = 2 + 7 = 9
  // 所以返回 [0, 1]

  // 穷举法
  function twoSum(nums, target) {
    for (let i = 0; i < nums.length; i++) {
      for (let j = i + 1; j < nums.length; j++) {
        if (nums[i] + nums[j] === target) {
          return [i, j];
        }
      }
    }
  }

  // hashMap
  function twoSum(nums, target) {
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
      let diff = target - nums[i]; // 计算差值
      if (map.has(diff)) { // 如果差值存在直接返回对应索引
        return [map.get(diff), i];
      } else { // 如果不存在直接存起来
        map.set(nums[i], i);
      }
    }
  }
  console.log(twoSum([2, 7, 11, 15], 9))
  console.log(twoSum([1, 2, 3, 4, 5, 6], 10));

  // 双指针
  // 准备两个指针，left执行数组开始，right执行数组结束
  // 如果 nums[left] + nums[right] = target，那么返回 nums[left]  nums[right]
  // 如果 nums[left] + nums[right] > target，那么说明应该缩小和，right指针左移
  // 如果 nums[left] + nums[right] < target，那么说明应该扩大和，left指针右移
  // 整个过程就是两个指针，根据所执行的数的和大小，来不断向中间移动查找的过程
  // 代码如下

  function twoSum(nums, target) {
    let left = 0,
      right = nums.length - 1;
    while (left < right) {
      let sum = nums[left] + nums[right];
      if (sum > target) {
        right--;
      } else if (sum < target) {
        left++;
      } else {
        return [left, right];
      }
    }
  }
  console.log(twoSum([2, 7, 9, 11], 9));
}

{
  // 实现 strStr() 函数。
  // 给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
  // 示例 1:
  // 输入: haystack = "hello", needle = "ll"
  // 输出: 2
  // 示例 2:
  // 输入: haystack = "aaaaa", needle = "bba"
  // 输出: -1
  // 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
  // 对于本题而言，当 needle 是空字符串时我们应当返回 0 。

  // 法一
  function strStr(haystack, needle) {
    if (needle === '') {
      return 0;
    }
    for (let i = 0; i < haystack.length - needle.length; i++) {
      if (haystack[i] === needle[0]) {
        var flag = true;
        for (let j = 0; j < needle.length; j++) {
          if (haystack[i + j] !== needle[j]) {
            flag = false;
            break;
          }
          if (flag) {
            return i;
          }
        }
      }
    }
    return -1;
  }

  // 法二
  function strStr(haystack, needle) {
    if (needle === '') {
      return 0;
    }
    for (let i = 0; i < haystack.length - needle.length; i++) {
      if (haystack[i] === needle[0]) {
        if (haystack.substring(i, i + needle.length) === needle) {
          return i;
        }
      }
    }
    return -1;
  }

  // 法三
  function strStr(haystack, needle) {
    return haystack.indexOf(needle);
  }
}

let list = [
  {
    title: '其它',
    value: 'channel-其它',
    key: 'channel-其它',
    children: [
      {
        title: '马东',
        value: 'albb',
        key: 'albb',
        children: [
          {
            title: '李三',
            value: 'lisan',
            key: 'lisan',
          },
          {
            title: '王五',
            value: 'wangwu',
            key: 'wangwu',
          },
        ],
      },
      {
        title: '王楠',
        value: 'jingdong',
        key: 'jingdong',
      },
    ],
  },
  {
    title: '保分期内测渠道',
    value: 'channel-保分期内测渠道',
    key: 'channel-保分期内测渠道',
    children: [
      {
        title: '梁兴',
        value: 'baofenqitest',
        key: 'baofenqitest',
      },
      {
        title: 'yanshou',
        value: 'aibaozhang',
        key: 'aibaozhang',
      },
      {
        title: '员工一',
        value: 'yuangong1',
        key: 'yuangong1',
      },
    ],
  },
];

console.log(list);

// 根据 path 递归查找 ，找到后直接return path所在对象
const treeSearch = (arr = [], path) => {
  let resObj = {};
  for (const obj of arr) {
    if (obj.url === rest.path) {
      resObj = { ...resObj, ...obj };
    } else if (obj?.children?.length) {
      resObj = { ...resObj, ...treeSearch(obj.children) };
    }
  }
  return resObj;
};

// 递归拉平
function flatten(arr = []) {
  return arr.reduce((lastRes, item, index) => {
    if (!Array.isArray(item.children)) {
      return lastRes.concat([item]);
    }
    return lastRes.concat(flatten(item.children));
  }, []);
}

// function flatten(arr = []) {
//   return arr.map(o => o.children ? [...flatten(o.children)] : [o]).flat()
// }

console.log(flatten(list));

console.log(strStr('hello', 'll'));

// 以下的代码如果迭代太深会出Stack错误，改写成不会出错的代码
var queue = '';
var nexItem = function () {
  var item = queue.pop();
  if (item) {
    nextItem();
  }
};

// 找出两个数组间不同的值:
const diff = (a, b) => {
  // let res = new Set(b)
  // return a.filter(v => res.has(v))

  return a.filter((v) => !b.includes(v));
};
console.log(diff([1, 2, 3, 2], [1, 2, 4, 2]));

// 编程：给一个DOM element d_elem， 对其所有的子Element进行遍历（包括其所有层次的子Element），对于每一个子 element，将其传给一个回调函数。
const traverse = (d_elem, callback) => { };

const traverse = (d_elem = [], callback) => {
  const resEle = handleEle(d_elem);
  callback(resEle);
};

const handleEle = (d_elem) => {
  return d_elem.reduce((lastItem, item) => {
    return Array.isArray(lastItem) ? handleEle(item) : item;
  }, []);
};

{
  // 获取最长无重复的字符串的长度
  // 给定 "abcabcbb" ，没有重复字符的最长子串是"abc"，那么长度就是3。
  let getMaxLongSubstring = function (s) {
    let res = 0; // 最长无重复字符串的长度
    let str = ''; // 无重复字符串
    let len = s.length;

    for (let i = 0; i < len; i++) {
      let char = s[i]; // 当前字符串
      let idx = str.indexOf(char);

      if (idx === -1) {
        // 遍历字符串，如果当前字符串内没有当前字符，这这个时候才会产生
        // 新字符串累加字符
        str += char;
        // 当前长度等于新字符串长度
        res = str.length;
      } else {
        // 如果当前字符串内有当前字符的话，从新截取字符串,截取到重复的这个字符
        console.log(str);
        str = str.substr(idx + 1) + char;
        console.log(str);
      }
    }

    return res;
  };
  console.log(getMaxLongSubstring('abcabcbb'));
}

// 60块砖头，60人搬，男人搬5块，女人搬3块，小孩2人搬一块，一次搬完，需要多少男人，多少女人，多少小孩，有几种组合方案
{
  for (let i = 1; i < 12; i++) {
    // 最多12个男人
    for (let j = 1; j < 20; j++) {
      // 最多20个女人
      let k = 60 - i - j; // 小孩数
      if (k % 2 === 0) {
        if (5 * i + 3 * j + k / 2 === 60) {
          console.log(`男人${i}，女人${j}个，小孩${k}个`);
        }
      }
    }
  }
}

// 判断一个数是否是质数
{
  let isPrime = function (num) {
    if (typeof num !== 'number' || !Number.isInteger(num)) {
      return false;
    }
    if (num < 2) {
      // 负数不是质数。同样的，1和0也不是
      return false;
    }
    if (num === 2) {
      // 2是质数中唯一的偶数
      return true;
    } else if (num % 2 === 0) {
      return false;
    }

    let len = Math.sqrt(num); // 开根号找到素数
    for (let i = 3; i <= len; i += 2) {
      if (num % i == 0) {
        // 说明num可以被其他的数字整除 也就说明num不是质数
        return false;
      }
    }
    return true;
  };
}

// 扁平化数组 正则实现
{
  let arr = [1, [2, [3, [4]], 5]];
  function flattenDeep(arr) {
    let str = JSON.stringify(arr);
    str = str.replace(/[\[|\]]/g, '');
    return str.split(',').map((v) => +v);
  }
  console.log(flattenDeep(arr));
}

// 斐波那契数列，要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）
// f(n) = f(n-1) + f(n-2)

// 解题提示：1 递归，注意递归缺陷 2 可以试试动态规划解法
{
  // 递归
  function factorial(n) {
    if (n < 2) {
      return n;
    }
    return factorial(n - 1) + factorial(n - 2);
  }

  // 递归记忆忆化
  // 使用一个数组缓存计算过程的值
  function factorial(n, memory = []) {
    if (n < 2) {
      return n;
    }

    if (!memory[n]) {
      memory[n] = factorial(n - 1, memory) + factorial(n - 2, memory);
    }

    // 0 1 2 3 5 8
    return memory[n];
  }

  // 动态规划解法
  function factorial(n) {
    if (n <= 1) {
      return n;
    }

    let i = 1; // 索引
    let pre = 0; // 上一个数值
    let current = 1; // 当前数值
    let result = 0; // 结果初始值

    while (i++ < n) {
      result = pre + current;
      pre = current; // 当前数赋值给上一个数
      current = result; // 结果赋值给当前数
    }

    return result;
  }
}

// 统计一个数字在排好序的数组中出现的位置
// 提示：有多种解法，试着分析那种解法更好
{
  // 本题有好几种解法
  // 1 直接遍历数组，判断前后得值是否相同，找到元素开始位置和结束位置，时间复杂度o(n)
  // 2 使用二分法查找找到目标值，在向前向后遍历，找到所有的数，比上面略优，时间复杂度是o(n)
  // 3 使用二分法查找，分别找到第一个目标和最后一个目标的位置。时间复杂度o(logn)

  // 使用二分法查找数组中的某个数
  function binarySerch(data, arr, start, end) {
    if (start > end) {
      return -1;
    }

    let mid = Math.floor((start + end) / 2);
    if (data === arr[mid]) {
      return mid;
    } else if (data < arr[mid]) {
      return binarySerch(data, arr, start, mid - 1);
    } else {
      return binarySerch(data, arr, mid + 1, end);
    }
  }

  // console.log(binarySerch(3, [1,3,5,7,9], 0, 4))

  // 找到第一次和最后一次出现的位置，我们只需对上面的代码稍加变形
  // 第一次位置：找到目标值，并且前一位的数字和当前值不相等
  // 最后一次位置：找到目标值，并且后一位的数字和当前值不相等

  function getFirstK(data, first, last, k) {
    if (first > last) return -1;

    let mid = Math.floor((first + last) / 2);
    if (data[mid] === k) {
      if (data[mid - 1] !== k) {
        return mid;
      } else {
        return getFirstK(data, first, mid - 1, k);
      }
    } else if (data[mid] > k) {
      return getFirstK(data, first, mid - 1, k);
    } else if (data[mid] < k) {
      return getFirstK(data, mid + 1, last, k);
    }
  }

  function getLastK(data, first, last, k) {
    if (first > last) return -1;

    let mid = Math.floor((first + last) / 2);
    if (data[mid] === k) {
      if (data[mid + 1] !== k) {
        return mid;
      } else {
        return getLastK(data, first, mid - 1, k);
      }
    } else if (data[mid] > k) {
      return getLastK(data, first, mid - 1, k);
    } else if (data[mid] < k) {
      return getLastK(data, mid + 1, last, k);
    }
  }

  function getNumberOfK(data, k) {
    if (data && data.length && k !== null) {
      // 第一次出现的位置
      let firstIndex = getFirstK(data, 0, data.length - 1, k);
      // 最后一次出现的位置
      let lastIndex = getLastK(data, 0, data.length - 1, k);
      if (firstIndex !== -1 && lastIndex !== -1) {
        return lastIndex - firstIndex + 1;
      }
    }
    return 0;
  }

  console.log(getNumberOfK([1, 3, 3, 5, 7, 9], 3));
}

// 输入一个字符串，按字典序打印出该字符串的所有排列。
// 例如输入字符串abc，则打印出由字符a，b，c所能排列出来的所有字符串abc,acb,bac,bca,cab,cba
{
  // 回溯法
  function Permutation(str) {
    if (!str) {
      return str;
    }

    let len = str.length,
      result = [],
      s = '';
    str = str.split('');
    str.sort();

    Permutate(str);
    result = [...new Set(result)]; // 去重
    return result.toString();

    function Permutate(str) {
      if (str.length === 0) {
        result.push(s);
      } else {
        let marked = new Set();
        for (let i = 0; i < str.length; i++) {
          if (!marked.has(str[i])) {
            let char = str.splice(i, 1);
            s += char;
            Permutate(str);
            str.splice(i, 0, char); // 把取出来的字符重新压回剩余字符串里
            s = s.slice(0, s.length - 1); // 把出去来的字符从排列结果里删除
            marked.add(char); // 标记该字符已经取过
          }
        }
      }
    }
  }
  console.log(Permutation('abc'));
}

// 实现一个函数，将一个字符串种的每个空格替换成%20
// 例如：'We are happy' 经过替换之后 'We%20are%20happy'
// 要求：不能用正则和内置函数
{
  function replaceStr(str) {
    let res = '';
    for (let i = 0; i < str.length; i++) {
      if (str[i] === ' ') {
        res += '%20';
      } else {
        res += str[i];
      }
    }
    return res;
  }
}

// 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
// 你可以假设数组是非空的，并且给定的数组总是存在多数元素
{
  function getNums(arr) {
    // 哈希表法 遍历两次，时间复杂度是O(n), 空间复杂度O(n)
    // let map = new Map(), res = 0, len = Math.floor(arr.length / 2)
    // for (let i = 0; i < arr.length; i++) {
    //   if (!map.has(arr[i])) {
    //     map.set(arr[i], 1)
    //   } else {
    //     map.set(arr[i], map.get(arr[i]) + 1)
    //   }
    // }
    // console.log(map)
    // for (const [key, value] of map) {
    //   if (key > len) {
    //     res = value
    //   }
    // }
    // return res

    // 摩尔投票算法
    // 题目说了只有一个数字出现的次数超过数组长度的一半，也就是说，这个数字出现的总数比其他他是数字出现的次数之和还要多
    // 定义变量 result 和 times。第一次遍历的时候
    // times = 0 那么 result 等于当前元素， times = 1
    // times != 0 且 result != 当前元素, times 减 1
    // times != 0 且 result = 当前元素，times 加 1
    // 遍历完成后， result就是数组中出现超过一半的数字了

    let times = 0,
      result = 0;
    arr.forEach((n) => {
      if (times === 0) {
        times = 1;
        result = n;
      } else if (result === times) {
        times++;
      } else {
        times--;
      }
    });
    return result;
  }
  console.log(getNums([1, 2, 3, 4, 5, 1, 1, 1, 6]));
}

// 从扑克牌中随机抽取5张扑克牌，判断是不是顺子，即这5张牌是不是连续的
// 2~10为数字本身，A为1，J为11，Q为12，K为13，大小王为0，可以看成任意数字。
// A不能视为14
{
  // 具体算法流程
  // 1 首先对数组进行排序
  // 2 排除数组中大小王（0）
  // 3 统计数组中所有相邻数之间的间隔
  // 4 同时还需要排除对子的情况，如果出现了对子，肯定不可能是顺子，0除外
  // 5 最后判断间隔值，如果大于4，说明可以组成顺子

  function isStaright(nums) {
    // 从小到大排序
    let minSort = nums.sort((a, b) => a - b);
    // 记录每个数组之间的大差值，反正不能大于4
    let sum = 0;
    // 不能超过4
    for (let i = 0; i < 4; i++) {
      // 忽略大小王也就是0
      if (minSort[i] === 0) {
        continue;
      } else if (minSort[i] === minSort[i + 1]) {
        // 排除对子
        return false;
      } else {
        // 记录差值
        sum = sum + minSort[i + 1] - minSort[i];
      }
    }
    // 差值如果超过4说明不是顺子
    return sum < 5;
  }
}

{
  // 出入一个正整数数组，把数组里面的所有数字拼接起来排成一个数，
  // 输出能拼接出的所有数字中最小的一个

  // 方法一：暴力法
  // 暴力法虽然能通过回溯得到所有可能的排列结果，然后从其中挑选出最小的数字
  // 这种方法最容易得到，虽然得到正确得结果，但是时间复杂度过高

  // function minNumber(nums) {
  //   const result = []
  //   permutation(nums, 0, result)
  //   result.sort((a, b) => {
  //     if (a < b) return -1
  //     if (a > b) return 1
  //     return 0
  //   })
  // }

  // function permutation(nums, start, result) {
  //   if (start === nums.length) {
  //     result.push(nums.join(''))
  //     return
  //   }

  //   for(let i = start; i < nums.length; i++) {
  //     [nums[i], nums[start]] = [nums[start], nums[i]]
  //     permutation(nums, start + 1, result)
  //     [nums[start], nums[i]] = [nums[i], nums[start]]
  //   }
  // }

  // 方法二：快速排序
  // 使用快速排序可以将数字正确得放在位置上，从而满足要求，例如对于数组[3, 32]来说，他有两种排列方法：332 323
  // 显然323符合题目的要求，那么在快排中，就因该比较332和323，然后返回正确顺序
  // 在js中，可以通过参数将自定义的【排序依据】作为函数传入sort中，这个函数的逻辑是：
  // 如果a + b < b + a,说明 ab 比 ba 小，a应该在b前面，返回-1
  // 如果a + b > b + a,说明 ab 比 ba 大，a应该在b后面，返回1
  // 如果相等返回0

  function minNumber(nums) {
    nums.sort((a, b) => {
      let s1 = a + '' + b;
      let s2 = b + '' + a;
      if (s1 > s2) return 1;
      if (s1 < s2) return -1;
      return 0;
    });
    return nums.join('');
  }
  // 时间复杂度是O(NlogN)，空间复杂度是O(1)
}

{
  // 用两个栈来实现一个队列，完成队列的push和pop操作。队列中的数据为int类型
  // 拓展思考 用两个队列来实现一个栈

  // 参考
  // 栈的特性是后入先出。根据题目提示，使用两个栈即可，一个栈 inStack 用来存储插入队列的数组，一个栈 outStack 用来从队列中去除数据
  // 算法分为入队和出队过程，
  // 入队过程放入： inStack 中
  // 出队过程： outStack不为空弹出元素，outStack为空，将 inStack中元素以此弹出，放入到 outStack 中
  // （在数据转移过程中，顺序已经从后入先出变为先入先出）
  // 时间复杂度是O(n)，空间复杂度是O(n)

  function CQuene() {
    this.inStack = [];
    this.outStack = [];
  }

  CQuene.prototype.appendTail = function (value) {
    this.inStack.push(value);
  };

  CQuene.prototype.deleteHead = function () {
    const { inStack, outStack } = this;
    if (outStack.length) {
      return outStack.pop();
    } else {
      while (inStack.length) {
        outStack.push(inStack.pop());
      }

      return outStack.pop() || -1;
    }
  };

  // 拓展思考：用两个队列实现一个栈
  // 类似的，用两个队列来实现一个栈，但是由于队列是先进先出，无论怎么倒换，都不可能逆序队列，所以处理思路还是不一样的
  // 准备两个队列 q1 q2 算法过程发分别为入栈和出栈

  // 入栈过程：
  // q1为空，放入q2
  // q2为空，放入q1
  // 均为，默认空放入q1

  // 出栈过程：
  // q1为空
  // 依次取出q2中的元素（除了最后一个），并且放入q1
  // 取出q2最后一个元素，返回结果
  // q2为空
  // 依次取出q1中的元素（除了最后一个），并且放入q2
  // 取出q1最后一个元素，返回结果

  // 时间复杂度是O(n)，空间复杂度是O(n)
}

{
  // 数组反转

  // 数组长度为3如下
  // 1 2 3
  // 3 2 1

  // 数组长度为4如下
  // 1 2 3 4
  // 4 2 3 1
  // 4 3 2 1

  // 数组长度为5如下
  // 1 2 3 4 5
  // 5 2 3 4 1
  // 5 4 3 2 1

  // 以上得出结论长度为n的数组需要交换n/2 + 1次

  let arr = [1, 2, 3, 4, 5, 6];
  for (let i = 0; i < arr.length / 2; i++) {
    [arr[i], arr[arr.length - i - 1]] = [arr[arr.length - i - 1], arr[i]];
  }
  console.log(arr);
}

{
  // 二个超大正整数的值相加，返回结果，只能用es5
  function add(str1, str2) {
    let arr1 = (str1 + '').split('');
    let arr2 = (str2 + '').split('');
    let extra = false; // 是否进位
    let sum = 0;
    let res = '';

    while (arr1.length || arr2.length || extra) {
      // pop方法从尾部删除，遍历一次，两个数组的末尾数相加
      let p1 = arr1.pop(),
        p2 = arr2.pop();
      sum = (p1 ? +p1 : 0) + (p2 ? +p2 : 0) + extra;
      // 按位取反
      // sum = ~~arr1.pop() + ~~arr2.pop() + extra
      res = (sum % 10) + res;
      // sum大于10进位
      extra = sum > 10;
    }

    return res;
  }

  console.log(add('111111111111', '2222222222222'));
}

{
  // 给定一个正整数n，将其拆分为至少两个正整数的和，并且使这些这正整数的乘积最大化，返回你可以获得的最大乘积

  // 参考答案题目中至少可以拆分为两个，说明n是大于1的正整数
  // 对于7来说, 可以拆成3+4，最大乘积使12
  // 对于8来水，可以拆成3+3+2，最大乘积是18

  // 解法1：动态规划法

  // 状态数组dp[i]表示：数字 i 表示可以拆分为至少两个正整数的和的最大乘积
  // 为了方便计算dp[i]数组的长度是n+1，初始值为1
  // 显然dp[2] = 1，外层循环从3开始遍历到 n 停止，内层循环 j 从1开始到 i 之前停止,
  // 他代表数字 i 可以拆分为 j + （i - j)，单是 j *（i - j)，不一定是最大乘积，因为 i - j 不一定大于dp[i - j]
  // (数字i - j 拆分成整数之和的最大乘积)，这里要选最大值最为dp[i]的结果
  // 时间复杂度是O(n2)，空间复杂度是O(n)，代码如下：

  function integerBreak(n) {
    const dp = new Array(n + 1).fill(1);

    for (let i = 3; i <= n; i++) {
      for (let j = 1; j <= i; j++) {
        dp[i] = Math.max(dp[i], j * (i - j), j * dp[i - j]);
      }
    }

    return dp[n];
  }

  // 解法2：贪心法

  // 解题的整体思路是
  // n 除以 3 的结果是 a，余数是b
  // 当a = 0; 直接将 a 个 3 相乘
  // 当a = 1; 直接将 (a - 1) 个 3 相乘，在乘以 4
  // 当a = 2; 直接将 a 个 3 相乘，在乘以 2
  // 时间复杂度O(1)，空间复杂度是O(1)，代码如下：

  function integerBreak(n) {
    if (n === 2) {
      return 1; // 1 * 1
    }

    if (n === 3) {
      return 2; // 2 * 1
    }

    // a的含义：n拆成的3的个数
    let a = Math.floor(n / 3);
    let b = n % 3;

    // n是3的倍数
    if (b === 0) {
      return Math.pow(3, a);
    }
    // n 是 3k + 1，例如7，拆成3，3，1，由于1对于结果没有贡献，所以最后的3，1换成4
    if (b === 1) {
      return Math.pow(3, a - 1) * 4;
    }
    // n 是 3k + 2，例如8，拆成3，3，2
    if (b === 2) {
      return Math.pow(3, a) * 2;
    }
  }
}

{
  // 判断一个int整数是否是自己的回文数，不能使用额外的空间来操作
  // 例如
  // 121 (121 === 121) => true
  // -121 (-121 !=== 121-) => false
  // 10 (10 !== 01) => false
  // 提示：如果你想用字符串解答是不可以的，因为不能使用额外的空间来操作
  // 你也可以反转整数，如果你之前做过leetcode 7，你会知道反转后的值可能超过integer最大值

  // 双指针
  function isPalindromeNum(num) {
    if (num < 0) return false;
    if (num < 10) return true;

    let arr = num.toString().split('');
    let left = 0;
    let right = arr.length - 1;
    let a = Math.floor(arr.length / 2);

    if (arr[left] !== arr[right]) return false;

    while (left < a) {
      left++;
      right--;
    }

    // 左指针移动到a的位置，就是回文数
    if (left === a) return true;

    return false;
  }

  function isPalindromeNum(num) {
    if (num < 0) return false;
    if (num < 10) return true;

    let arr = num.toString().split('');
    let arr1 = [];
    for (let i = arr.length - 1; i >= 0; i--) {
      arr1.push(arr[i]);
    }

    return arr.toString() === arr1.toString();
  }

  // 以上方法都用了额外空间 比如Array String

  // 用反转正整数法
  function isPalindromeNum(x) {
    // x < 0 or x > 2^32 - 1, false
    if (x < 0 || x > Math.pow(2, 32) - 1) return false;
    if (x < 10) return true;

    // keep x
    let num = x;

    // 先抓出最高位数，换成个位数
    let recNum = x % 10;
    x = Math.floor(x / 10);

    // 将 recNum * 10，在抓去最高位数加到recNum上
    while (x !== 0) {
      recNum = recNum * 10;
      recNum = recNum + (x % 10);
      x = Math.floor(x / 10);
    }

    return num === recNum;
  }
}

{
  // 给定一个排序数组，你需要在原地删除出现重复的元素，是的每个元素只出现一次，返回删除后数组的长度。
  // 不要使用额外的数组空间，你必须在原地修改输入数组，并在使用O(1)额外空间的条件下完成

  // 例如 nums = [1,1,2] 返回新的长度是2；原数组的前两个数被修改为1，2
  // 例如 nums = [0,0,0,1,1,2,2,3,4] 返回新的长度5，原数组的前五个书被修改0，1，2，3，4
  // 不需要考虑新数组中超出长度的元素

  // 提示：
  // 使用一个count来记录有多少个不重复的元素
  // 当数组中当前元素和下一个元素重复，就跳过，否则就放在数组中

  function removeDuplicates(nums) {
    if (nums.length === 0 || !nums) return 0;
    if (nums.length === 1) return 1;

    let count = 0;
    for (let i = 0; i < nums.length; i++) {
      if (nums[count] !== nums[i]) {
        count++;
        nums[count] = nums[i];
      }
    }
    console.log(nums);
    return ++count;
  }
}

{
  // 给两个数组，编写一个函数来算出它们的交集
  // 例如 nums1 = [1,2,2,1] nums2 = [2,2] 输出[2]
  // 例如 nums1 = [4,9,5] nums2 = [9,4,9,8,4] 输出[9,4]

  function getNumsIntersection(nums1, nums2) {
    let hash1 = new Set(nums1); // 定义哈希数组
    let hash2 = new Set();

    for (let i = 0; i < nums2.length; i++) {
      if (hash1.has(nums2[i])) {
        hash2.add(nums2[i]);
      }
    }

    return [...hash2]; // 返回数组
  }

  function getNumsIntersection(nums1, nums2) {
    let result = [];
    let store; // 长数组
    let ary; // 短数组

    if (nums1.length > nums2.length) {
      store = nums1;
      ary = nums2;
    } else {
      store = nums2;
      ary = nums1;
    }

    for (let i = 0; i < store.length; i++) {
      const val = store[i];
      // if (ary.indexOf(val) > -1 && result.indexOf(val) === -1 ) {
      if (ary.includes(val) && !result.includes(val)) {
        result.push(val);
      }
    }

    return result;
  }
}

{
  // 加入你正在爬楼梯，需要n阶你才能到达楼顶
  // 每次可以爬一个或者2个台阶，你有多少种不同的方法可以爬到楼顶
  // 注意：给定n是正整数

  // 示例1：
  // 输入2 输出2
  // 解释有两种方法：
  // 1阶 + 1阶 和 2阶

  // 示例2
  // 输入3 输出3
  // 解释有三中方法：
  // 1阶 + 1阶 + 1阶 和 1阶 + 2阶 和 2阶 + 1阶

  // 参考答案
  // n = 1, result = 1
  // n = 2, result = 1+1 (爬1阶两次 + 一次爬2阶)
  // n = 3, result = 1+2 (前面两个case想加)
  // n = 4, result = 3+2 (前面两个case想加)
  // 其实这题就是算斐波那契数列

  function climbStairs(n) {
    if (n <= 1) {
      return 1;
    }

    let cur = 1;
    let prev = 1;
    // 斐波那契数列 f(n) = f(n-1) + f(n-2)
    for (let i = 2; i <= n; i++) {
      let temp = cur;
      cur = cur + prev;
      prev = temp;
    }

    return cur;
  }
}

{
  // 一人每次只能走一层楼梯或两层楼梯，问走到80层楼梯有多少种走法

  // 走到n层实际上是走(n-1)层+1层 或者是走到(n-2)层+2层
  // 实际上就是斐波那契数列 fn(n) = fn(n-1) + fn(n-2)

  function stairs(n) {
    if (n <= 0) throw Error('请输入正确的数字');
    if (n === 1) return 1;
    if (n === 2) return 2;

    return stairs(n - 1) + stairs(n - 2);
  }
}

{
  // 实现一个函数，给定一个数组 [1,0,2,3,4,-1,-3] 输出任意两个和为0的下标
  function getIndex(arr) {
    let result = [];
    // 暴力双循环
    // for (let i = 0; i < arr.length; i++) {
    //   for (let j = i + 1; j < arr.length; j++) {
    //     if (arr[i] + arr[j] === 0) {
    //       result.push([i, j])
    //     }
    //   }
    // }
    // hashMap
    let map = new Map();
    for (let i = 0; i < arr.length; i++) {
      map.set(arr[i], i);
      let diff = -arr[i];
      if (map.has(diff)) {
        return [map.get(arr), i];
      }
    }
    return result;
  }
}

{
  // 二分查找法，使用递归和非递归实现
  // 有序数组 存在返回目标索引，不存在返回-1

  // 非递归法
  function binSearch(arr, target) {
    let mid = 0;
    let start = 0;
    let end = arr.length - 1;
    while (start <= end) {
      mid = (end - start) / 2 + start;
      if (target < arr[mid]) {
        // 左边找
        end = mid - 1;
      } else if (target >= arr[mid]) {
        // 右边找
        start = mid + 1;
      } else {
        return mid;
      }
    }
    return -1;
  }

  // 递归法
  function binSearch(arr, start, end, target) {
    let mid = (end - start) / 2 + start;
    if (arr[mid] === target) return mid;

    if (target < arr[mid]) {
      binSearch(arr, start, mid - 1, target);
    } else if (target >= arr[mid]) {
      binSearch(arr, mid + 1, end, target);
    } else if (start >= end) {
      return -1;
    }

    return -1;
  }
}

{
  // 找出字符串中出现字符出现的字母
  let str = 'asdabjgasd';
  let o = {};
  for (let i = 0; i < str.length; i++) {
    let char = str[i];
    if (!o[char]) {
      o[char] = 1;
    } else {
      o[char] = o[char] + 1;
    }
  }
  console.log(o);

  let max = 0;
  let maxChar = null;
  for (const key in o) {
    if (max < o[key]) {
      max = o[key];
      maxChar = key;
    }
  }

  console.log(`出现最多的字符是：${maxChar}，出现了：${max}次`);
}

{
  // 给你一个包含 n 个整数的数组 num，判断 num 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
  // 请你找出所有满足条件且不重复的三元组。
  // 示例
  // 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
  // 思路：
  // 三数求和问题实际可以继续延续两树求和问题，固定其中一个数，在剩下的两个数中找两树之和，和这个固定的数相加是否等于0；
  // 咋一看可能需要三层循环才能解决，但是采用双指针，会大大提升效率，双指针可以避免过度循环，利用空间换取时间；
  // 注意，双指针在求和，比较大小类的题目时，有个前提，就是该数组必须有序；
  // 所以第一步就是对数组排序；
  // 然后在遍历，遍历到哪个数字，就固定哪个数字，然后左指针指向固定数字后面的一个，右指针指向数组末尾，让左右指针向中间移动；
  // 每次指针移动一个位置，计算两个指针指向数字之和加上固定数字是否等于0，如果是就得到一个目标值；否则就分两种情况:
  // 相加之和大于0，说明右侧的数字偏大了，右指针左移；
  // 相加之和小于0，说明左侧的数字偏小了，左指针右移；
  // 另外要求，三元组是不重复的，因此要需要做一个重复元素跳过的过程;
  /**
   * @param {number[]} nums
   * @return {number[][]}
   */
  function threeNums(nums, target = 100) {
    let res = [];
    let n = nums.length;

    // 边界判断
    if (nums === null || n < 3) {
      return res;
    }
    // 数组排序，保证数组是递增的
    nums.sort((a, b) => a - b);

    // 这里遍历到倒数第三个数就可以了，因为左右指针会遍历其中两个数
    for (let i = 0; i < n - 2; i++) {
      // 遇到重复数字跳过
      if (i > 0 && nums[i] === nums[i - 1]) {
        continue;
      }

      // 左右两个指针
      let left = i + 1;
      let right = n - 1;
      while (left < right) {
        // 定义三个数之和，然后和目标值对比
        let sum = nums[i] + nums[left] + nums[right];
        if (sum === target) {
          // 和目标值相等，push进结果数组，然后left指针右移，right指针左移
          res.push([nums[i], nums[left], nums[right]]);
          left++;
          right--;
          // // 处理左指针重复
          // while (nums[left] === nums[left - 1]) {
          //   left++;
          // }
          // // 处理右指针重复
          // while (nums[right] === nums[right + 1]) {
          //   right--;
          // }
        } else if (sum > target) {
          // 比目标值大，right指针应该左移
          right--;
          // // 处理右指针重复
          // while (nums[right] === nums[right + 1]) {
          //   right--;
          // }
        } else {
          // 比目标值小，left指针应该左移
          left++;
          // // 处理左指针重复
          // while (nums[left] === nums[left - 1]) {
          //   left++;
          // }
        }
      }
    }
    return res;
  }
  console.log(threeNums([2, 11, 20, 160, 3, 1, 77, 12]));
  console.log(threeNums([-1, 0, 1, 2, -1, -4], 0));
  // 左右指针一起从两边向中间位置相互迫近，这样的特殊指针形态，被称为“对撞指针”。
  // 在什么时候我们要联想到双指针方法呢？
  // 注意两个关键字：有序、数组
  // 普通双指针走不通，立马想对撞指针
}

{
  // 给定一个字符串 'abca' 返回第一个不重复的字母
  function firstNoRepeatChar(str) {
    // 哈希表
    let o = {};
    for (let i = 0; i < str.length; i++) {
      if (o[str[i]]) {
        o[str[i]]++;
      } else {
        o[str[i]] = 1;
      }
    }

    let ret = -1;
    for (let i = 0; i < str.length; i++) {
      // 取出当前哈希表当中本次循环的字符串是1的字符就是结果
      if (o[str[i]] === 1) {
        ret = str[i];
        break;
      }
    }
    return ret;
  }

  // function firstNoRepeatChar(str) {
  //   let len = str.length
  //   let num = 0
  //   let ret = ''
  //   for (let i = 0; i < len; i++) {
  //     for (let j = 0; j < len; j++) {
  //       if (i !== j && str[i] !== str[j]) {
  //         num++
  //       }
  //     }
  //     if (num === len - 1) {
  //       ret = str[i]
  //       break
  //     }
  //     num = 0
  //   }
  //   return ret
  // }

  function firstNoRepeatChar(str) {
    let len = str.length;
    let ret = '';
    for (let i = 0; i < len; i++) {
      // 计数器
      let num = 0;
      for (let j = 0; j < len; j++) {
        // 遇到重复且不是本身 计数器累加 且直接跳出本次循环进行下一次对比
        if (i !== j && str[i] === str[j]) {
          num++;
          break;
        }
      }
      if (num === 0) {
        ret = str[i];
        break;
      }
    }
    return ret;
  }

  function firstNoRepeatChar(str) {
    let ret = '';
    for (let i = 0; i < str.length; i++) {
      let s = str;
      test = s.split();
      // 当前字符串数组，去掉当前循环的字符
      test = test.splice(i, 1);
      // 判断剩下字符数组
      if (test.indexOf(str[i]) === -1) {
        ret = str[i];
        break;
      }
    }
    return ret;
  }
  console.log(firstNoRepeatChar('abca'));
}

{
  // js随机选取10-100之间的10个数且不重复的数字，存入一个数组，并排序

  function getRandom(start, end) {
    return Math.floor(Math.random() * (end - start + 1) + start);
  }

  function sortNum(arr) {
    return arr.sort((a, b) => a - b);
  }

  function getNums() {
    let set = new Set();
    while (set.size < 10) {
      set.add(getRandom(10, 100));
    }
    let arr = [...set];
    arr = sortNum(arr);
    return arr;

    // let arr = []
    // for (let i = 0; i < 10; i++) {
    //   let n = getRandom(10, 100)
    //   if (arr.indexOf(n) === -1) {
    //     arr.push(n)
    //   } else {
    //     i--
    //   }
    // }
    // arr = sortNum(arr)
    // return arr
  }
}

{
  // 找出前k个最大的元素
  // 法一 暴力全排
  function findK(arr, k) {
    arr = arr.sort((a, b) => a - b);
    return arr[k - 1];
  }

  // 法二 冒泡半排
  function findK(arr, k) {
    for (let i = 0; i < k; i++) {
      for (let j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
          [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        }
      }
    }
    return arr[arr.length - k];
  }
}

{
  // js数组和树形结构数据相互转换
  let arr = [
    { id: 2, name: '部门B', parentId: 0 },
    { id: 3, name: '部门C', parentId: 1 },
    { id: 1, name: '部门A', parentId: 2 },
    { id: 4, name: '部门D', parentId: 1 },
    { id: 5, name: '部门E', parentId: 2 },
    { id: 6, name: '部门F', parentId: 3 },
    { id: 7, name: '部门G', parentId: 2 },
    { id: 8, name: '部门H', parentId: 4 },
  ];

  /*
   * 数组转树 非递归求解
   * 利用数组和对象相互利用 时间复杂度O(n)
   * @param {Object} list
   */
  function toTree(list = [], parentId = 0) {
    let obj = {};
    let result = [];
    // 讲数组转化为键值对结构（这里的数组和对象相互引用）
    list.map((el) => (obj[el.id] = el));

    for (let i = 0; i < list.length; i++) {
      let id = list[i].parentId;
      if (id === parentId) {
        result.push(list[i]);
        continue;
      }

      if (obj[id].children) {
        obj[id].children.push(list[i]);
      } else {
        obj[id].children = [list[i]];
      }
    }
    return result;
  }

  /*
   * 数组转树 递归求解
   */
  function toTree(list, parId) {
    function loop(parId) {
      let result = [];
      for (let i = 0; i < list.length; i++) {
        let el = list[i];
        if (el.parentId === parId) {
          el.children = loop(el.id);
          result.push(el);
        }
      }
      return result;
    }
    return loop(parId);
  }
}

{
  // 给定一个包含 m x n 个元素的矩阵（m 行, n 列），可以理解为二维数组，请按照顺时针螺旋顺序，返回矩阵中的所有元素。

  // 例如
  // 输入: [
  // [ 1, 2, 3 ],
  // [ 4, 5, 6 ],
  // [ 7, 8, 9 ] ]
  // 输出: [1,2,3,6,9,8,7,4,5]

  // 输入: [
  // [1, 2, 3, 4],
  // [5, 6, 7, 8],
  // [9,10,11,12] ]
  // 输出: [1,2,3,4,8,12,11,10,9,5,6,7]

  /*
   * @param {number[][]} matrix
   * @return {number[]}
   */
  function traverseLayer(m, startRow, endRow, startCol, endCol, res) {
    if (startRow === endRow) {
      // 一列的情况
      // [
      //   [1],
      //   [2],
      //   [3]
      // ]
      for (let i = startCol; i <= endCol; i++) {
        res.push(m[startRow][i]);
      }
    } else if (startCol === endCol) {
      // 一行的情况
      // [[1], [2], [3]]
      for (let i = startRow; i <= endRow; i++) {
        res.push(m[i][startRow]);
      }
    } else {
      let curRow = startRow;
      let curCol = startCol;

      while (curCol < endCol) {
        res.push(m[curRow][curCol]);
        curCol++;
      }

      while (curRow < endRow) {
        res.push(m[curRow][curCol]);
        curRow++;
      }

      while (curCol > startCol) {
        res.push(m[curRow][curCol]);
        curCol--;
      }

      while (curRow > startRow) {
        res.push(m[curRow][curCol]);
        curRow--;
      }
    }
  }

  function spiralOrder(matrix) {
    if (matrix === void 0 || matrix.length == 0 || matrix[0].length === 0) {
      return [];
    }

    let res = [];
    let startRow = 0;
    let endRow = matrix.length - 1;
    let startCol = 0;
    let endCol = matrix[0].length - 1;

    while (startRow <= endRow && startCol <= endCol) {
      traverseLayer(matrix, startRow, endRow, startCol, endCol, res);
      startRow++;
      endRow--;
      startCol++;
      endCol--;
    }

    return res;
  }

  let m = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12],
    [13, 14, 15, 16],
  ];
  console.log(spiralOrder(m));
}

{
  // 给你一个仅由数字 6 和 9 组成的正整数 num。
  // 你最多只能翻转一位数字，将 6 变成 9，或者把 9 变成 6 。
  // 请返回你可以得到的最大数字。

  // 示例 1：
  // 输入：num = 9669
  // 输出：9969
  // 解释：
  // 改变第一位数字可以得到 6669 。
  // 改变第二位数字可以得到 9969 。
  // 改变第三位数字可以得到 9699 。
  // 改变第四位数字可以得到 9666 。
  // 其中最大的数字是 9969 。

  // 示例 2：
  // 输入：num = 9996
  // 输出：9999
  // 解释：将最后一位从 6 变到 9，其结果 9999 是最大的数。

  // 示例 3：
  // 输入：num = 9999
  // 输出：9999
  // 解释：无需改变就已经是最大的数字了。

  // 提示：
  // 1 <= num <= 10^4
  // num 每一位上的数字都是 6 或者 9 。

  const maximum69Number = function (num) {
    // 解法一 有点笨拙但是也解出来了
    // const nums = num;
    // // 将数组转化成字符串遍历
    // let arr = nums.toString().split('');
    // // 定义初始最大值
    // let max = num;
    // const maps = {
    //   '6': '9',
    //   '9': '6'
    // }
    // let index = 0;
    // for (let i = 0; i < arr.length; i++) {
    //   // 反转当前字符
    //   arr[index] = maps[arr[index]]
    //   const curNum = +arr.join('');
    //   if (curNum > max) max = curNum
    //   // 反转下次时，先讲当前字符反转回来
    //   arr[index] = maps[arr[index]]
    //   index++
    // }
    // return max

    // 解二
    // let arr = num.toString().split('');
    // // 遍历每一项当遇到6时变为9跳出循环,翻转一次，此时一定是最大的
    // for (let i = 0; i < arr.length; i++) {
    //   if (arr[i] === '6') {
    //     arr[i] = '9'
    //     break
    //   }
    // }
    // return +arr.join('')

    // 解三
    // 反转最高位是6的即可
    // 用replace api可完成
    return +(num + '').replace('6', '9');
  };
  console.log(maximum69Number(9669));
  console.log(maximum69Number(9996));
  console.log(maximum69Number(9999));
}

{
  // 在整数数组中，如果一个整数的出现频次和它的数值大小相等，我们就称这个整数为「幸运数」。
  // 给你一个整数数组 arr，请你从中找出并返回一个幸运数。
  // 如果数组中存在多个幸运数，只需返回 最大 的那个。
  // 如果数组中不含幸运数，则返回 - 1 。

  // 示例 1：
  // 输入：arr = [2, 2, 3, 4]
  // 输出：2
  // 解释：数组中唯一的幸运数是 2 ，因为数值 2 的出现频次也是 2 。

  // 示例 2：
  // 输入：arr = [1, 2, 2, 3, 3, 3]
  // 输出：3
  // 解释：1、2 以及 3 都是幸运数，只需要返回其中最大的 3 。

  // 示例 3：
  // 输入：arr = [2, 2, 2, 3, 3]
  // 输出：-1
  // 解释：数组中不存在幸运数。

  // 示例 4：
  // 输入：arr = [5]
  // 输出：-1

  const findLucky = function (arr) {
    let max = -1; // 最大幸运数字
    let obj = {}; // 映射对象
    for (let i = 0; i < arr.length; i++) {
      const el = arr[i];
      if (obj[el]) {
        obj[el]++;
      } else {
        obj[el] = 1;
      }
    }

    for (const key in obj) {
      if (+key === obj[key] && obj[key] > max) {
        max = obj[key];
      }
    }

    return max;
  };
  console.log(findLucky([2, 2, 3, 4]));
  console.log(findLucky([1, 2, 2, 3, 3, 3]));
  console.log(findLucky([2, 2, 2, 3, 3]));
  console.log(findLucky([5]));
}

{
  // 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

  // 示例 1：
  // 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
  // 输出：6
  // 解释：连续子数组 [4,-1,2,1] 的和最大，为 6

  // 示例 2：
  // 输入：nums = [1]
  // 输出：1

  // 示例 3：
  // 输入：nums = [0]
  // 输出：0

  // 示例 4：
  // 输入：nums = [-1]
  // 输出：-1

  // 示例 5：
  // 输入：nums = [-100000]
  // 输出：-100000

  /**
   * @param {number[]} nums
   * @return {number}
   */

  // 贪心算法，若当前指针元素之前的和小于0，则丢弃当前元素之前的数列
  var maxSubArray = function (nums) {
    var res = nums[0];
    var sum = 0;
    for (let i = 0; i < nums.length; i++) {
      if (sum > 0) {
        sum += nums[i];
      } else {
        sum = nums[i];
      }
      res = Math.max(res, sum);
    }
    return res;
  };
  console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]));
}

{
  // 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
  // 有效字符串需满足：
  // 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

  // 示例 1：
  // 输入：s = "()"
  // 输出：true

  // 示例 2：
  // 输入：s = "()[]{}"
  // 输出：true

  // 示例 3：
  // 输入：s = "(]"
  // 输出：false

  // 示例 4：
  // 输入：s = "([)]"
  // 输出：false

  // 思路分析
  // 遍历输入字符串
  // 如果当前字符为左半边括号时，则将其压入栈中
  // 如果遇到右半边括号时，分类讨论：
  // 如栈不为空且为对应的左半边括号，则取出栈顶元素，继续循环
  // 若此时栈为空，则直接返回false
  // 若不为对应的左半边括号，反之返回false
  // 使用数组来模拟，入为push，出为pop，即是栈。
  // 入为push，出为shift，即是队列。

  /**
   * @param {string} s
   * @return {boolean}
   */
  var isValid = function (s) {
    while (s.includes('[]') || s.includes('{}') || s.includes('()')) {
      s = s.replace('[]', '').replace('{}', '').replace('()', '');
    }
    s = s.replace('[]', '').replace('{}', '').replace('()', '');
    return s.length === 0;
  };

  var isValid = function (s) {
    if (s.length % 2 !== 0) return false; // 奇数不符合条件

    const stack = [];
    const map = {
      ')': '(',
      '}': '{',
      ']': '[',
    };
    for (const item of s) {
      // s[i] === '[' || s[i] === '{' || s[i] === '('
      if (['(', '{', '['].includes(item)) {
        // 左括号入栈
        stack.push(item);
      } else {
        // 右括号出栈 并和上一次入栈的左括号匹配
        var key = stack.pop();
        if (map[item] !== key) {
          return false;
        }
      }
    }
    return stack.length === 0;
  };
  console.log(isValid('()'));
  console.log(isValid('()[]{}'));
  console.log(isValid('(]'));
  console.log(isValid('([)]'));
  console.log(isValid('{[]}'));
}

{
  // 盛水最多的容器
  // 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
  // 说明：你不能倾斜容器。

  // 示例 1：
  // 输入：[1,8,6,2,5,4,8,3,7]
  // 输出：49
  // 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

  // 示例 2：
  // 输入：height = [1,1]
  // 输出：1

  // 示例 3：
  // 输入：height = [4,3,2,1,4]
  // 输出：16

  // 示例 4：
  // 输入：height = [1,2,1]
  // 输出：2

  // 思路
  // 面积 = 长 * 宽
  // 长度 = 两条垂直线段之间的距离
  // 宽度 = 两条垂直线段当中较短的一条
  // 木桶原理 容纳的水量取决于短板

  // 暴力破解
  function maxArea(height = []) {
    let max = 0; // 最大水容量
    for (let i = 0; i < height.length; i++) {
      for (let j = i + 1; j < height.length; j++) {
        let curr = (j - i) * Math.min(height[i], height[j]); // 当前水容量
        max = Math.max(max, curr);
      }
    }
    return max;
  }

  // 双指针
  function maxArea(height = []) {
    let max = 0; // 最大水容量
    let left = 0;
    let right = height.length - 1;
    while (left < right) {
      // 当前水容量
      let curr = (right - left) * Math.min(height[left], height[right]);
      max = Math.max(max, curr);
      height[left] < height[right] ? left++ : right--;
    }
    return max;
  }
  console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]));
}

{
  // 移动零
  // 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
  // 输入: [0, 1, 0, 3, 12];
  // 输出: [1, 3, 12, 0, 0];

  // 在此基础上附加了两个条件：
  // 必须在原数组上操作，不能拷贝额外的数组。
  // 尽量减少操作次数。

  // 我们可以借助双指针来进行求解，求解过程如下：
  // 1 初始化双指针 i 、j 指向数组头部索引 0。
  // 2 将 i 指针不断向右移动，j 指针负责提供交换的位置，当遇到非 0 数字时，将两个指针位置的数字交换，同时继续向右边移动两个指针。这样交换可以保证题目要求的非 0 数字相对顺序不变。
  // 3 当遇到 0 时，向右移动 i 指针，j 指针不动。
  // 4 循环完成时即可将所有的 0 移动到数组的末尾。

  let moveZeroes = function (nums) {
    let i = 0;
    let j = 0;
    while (i < nums.length) {
      if (nums[i] !== 0) {
        [nums[i], nums[j]] = [nums[j], nums[i]];
        i++;
        j++;
      } else {
        i++;
      }
    }
    return nums;
  };
  console.log(moveZeroes([0, 1, 0, 3, 12]));
  // 移动过程如下
  // 初始化 [0, 1, 0, 3, 12] i = 0 j = 0
  // 第一轮 [1, 0, 0, 3, 12] i = 1 j = 0
  // 第二轮 [1, 3, 0, 0, 12] i = 2 j = 1
  // 第三轮 [1, 3, 0, 0, 12] i = 3 j = 1
  // 第四轮 [1, 3, 12, 0, 0] i = 4 j = 2
  // 第五轮 [1, 3, 12, 0, 0] i = 5 j = 2 循环结束

  function moveZeroes(arr) {
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] == 0) {
        // 找到0的元素，删除，在放到数组尾部
        let temp = arr.splice(i, 1);
        arr[arr.length] = temp[0];
      }
    }
    return arr;
  }
}

{
  // 给定一个制定数组，类似于[1,3,4,9,19]，数组数量不定，找出最接近平均数的数字
  var getTargetNum = function (nums) {
    if (nums.length === 0) return 0;
    if (nums.length === 1) return nums[0];

    let index = 0; // 最接近平均数的索引
    let min = Math.max(...nums); // 记录最小的差值，默认取数组最大值
    // 平均值
    let average =
      nums.reduce((lastRes, item) => {
        return lastRes + item;
      }, 0) / nums.length;

    for (let i = 0; i < nums.length; i++) {
      // 当前差值
      let diff = Math.abs(nums[i] - average);
      if (min > diff) {
        min = diff;
        index = i;
      }
    }

    return nums[index];
  };
  console.log(getTargetNum([1, 3, 4, 9, 19]));
}
